home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 22 / PCPP #22.iso / Quake2 / q2source_12_11 / utils3 / bsp / qbsp3 / portals.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-11-19  |  21.0 KB  |  1,091 lines
  1.  
  2. #include "qbsp.h"
  3.  
  4.  
  5. int        c_active_portals;
  6. int        c_peak_portals;
  7. int        c_boundary;
  8. int        c_boundary_sides;
  9.  
  10. /*
  11. ===========
  12. AllocPortal
  13. ===========
  14. */
  15. portal_t *AllocPortal (void)
  16. {
  17.     portal_t    *p;
  18.     
  19.     if (numthreads == 1)
  20.         c_active_portals++;
  21.     if (c_active_portals > c_peak_portals)
  22.         c_peak_portals = c_active_portals;
  23.     
  24.     p = malloc (sizeof(portal_t));
  25.     memset (p, 0, sizeof(portal_t));
  26.     
  27.     return p;
  28. }
  29.  
  30. void FreePortal (portal_t *p)
  31. {
  32.     if (p->winding)
  33.         FreeWinding (p->winding);
  34.     if (numthreads == 1)
  35.         c_active_portals--;
  36.     free (p);
  37. }
  38.  
  39. //==============================================================
  40.  
  41. /*
  42. ==============
  43. VisibleContents
  44.  
  45. Returns the single content bit of the
  46. strongest visible content present
  47. ==============
  48. */
  49. int VisibleContents (int contents)
  50. {
  51.     int        i;
  52.  
  53.     for (i=1 ; i<=LAST_VISIBLE_CONTENTS ; i<<=1)
  54.         if (contents & i )
  55.             return i;
  56.  
  57.     return 0;
  58. }
  59.  
  60.  
  61. /*
  62. ===============
  63. ClusterContents
  64. ===============
  65. */
  66. int ClusterContents (node_t *node)
  67. {
  68.     int        c1, c2, c;
  69.  
  70.     if (node->planenum == PLANENUM_LEAF)
  71.         return node->contents;
  72.  
  73.     c1 = ClusterContents(node->children[0]);
  74.     c2 = ClusterContents(node->children[1]);
  75.     c = c1|c2;
  76.  
  77.     // a cluster may include some solid detail areas, but
  78.     // still be seen into
  79.     if ( ! (c1&CONTENTS_SOLID) || ! (c2&CONTENTS_SOLID) )
  80.         c &= ~CONTENTS_SOLID;
  81.     return c;
  82. }
  83.  
  84. /*
  85. =============
  86. Portal_VisFlood
  87.  
  88. Returns true if the portal is empty or translucent, allowing
  89. the PVS calculation to see through it.
  90. The nodes on either side of the portal may actually be clusters,
  91. not leafs, so all contents should be ored together
  92. =============
  93. */
  94. qboolean Portal_VisFlood (portal_t *p)
  95. {
  96.     int        c1, c2;
  97.  
  98.     if (!p->onnode)
  99.         return false;    // to global outsideleaf
  100.  
  101.     c1 = ClusterContents(p->nodes[0]);
  102.     c2 = ClusterContents(p->nodes[1]);
  103.  
  104.     if (!VisibleContents (c1^c2))
  105.         return true;
  106.  
  107.     if (c1 & (CONTENTS_TRANSLUCENT|CONTENTS_DETAIL))
  108.         c1 = 0;
  109.     if (c2 & (CONTENTS_TRANSLUCENT|CONTENTS_DETAIL))
  110.         c2 = 0;
  111.  
  112.     if ( (c1|c2) & CONTENTS_SOLID )
  113.         return false;        // can't see through solid
  114.  
  115.     if (! (c1 ^ c2))
  116.         return true;        // identical on both sides
  117.  
  118.     if (!VisibleContents (c1^c2))
  119.         return true;
  120.     return false;
  121. }
  122.  
  123.  
  124. /*
  125. ===============
  126. Portal_EntityFlood
  127.  
  128. The entity flood determines which areas are
  129. "outside" on the map, which are then filled in.
  130. Flowing from side s to side !s
  131. ===============
  132. */
  133. qboolean Portal_EntityFlood (portal_t *p, int s)
  134. {
  135.     if (p->nodes[0]->planenum != PLANENUM_LEAF
  136.         || p->nodes[1]->planenum != PLANENUM_LEAF)
  137.         Error ("Portal_EntityFlood: not a leaf");
  138.  
  139.     // can never cross to a solid 
  140.     if ( (p->nodes[0]->contents & CONTENTS_SOLID)
  141.     || (p->nodes[1]->contents & CONTENTS_SOLID) )
  142.         return false;
  143.  
  144.     // can flood through everything else
  145.     return true;
  146. }
  147.  
  148.  
  149. //=============================================================================
  150.  
  151. int        c_tinyportals;
  152.  
  153. /*
  154. =============
  155. AddPortalToNodes
  156. =============
  157. */
  158. void AddPortalToNodes (portal_t *p, node_t *front, node_t *back)
  159. {
  160.     if (p->nodes[0] || p->nodes[1])
  161.         Error ("AddPortalToNode: allready included");
  162.  
  163.     p->nodes[0] = front;
  164.     p->next[0] = front->portals;
  165.     front->portals = p;
  166.     
  167.     p->nodes[1] = back;
  168.     p->next[1] = back->portals;
  169.     back->portals = p;
  170. }
  171.  
  172.  
  173. /*
  174. =============
  175. RemovePortalFromNode
  176. =============
  177. */
  178. void RemovePortalFromNode (portal_t *portal, node_t *l)
  179. {
  180.     portal_t    **pp, *t;
  181.     
  182. // remove reference to the current portal
  183.     pp = &l->portals;
  184.     while (1)
  185.     {
  186.         t = *pp;
  187.         if (!t)
  188.             Error ("RemovePortalFromNode: portal not in leaf");    
  189.  
  190.         if ( t == portal )
  191.             break;
  192.  
  193.         if (t->nodes[0] == l)
  194.             pp = &t->next[0];
  195.         else if (t->nodes[1] == l)
  196.             pp = &t->next[1];
  197.         else
  198.             Error ("RemovePortalFromNode: portal not bounding leaf");
  199.     }
  200.     
  201.     if (portal->nodes[0] == l)
  202.     {
  203.         *pp = portal->next[0];
  204.         portal->nodes[0] = NULL;
  205.     }
  206.     else if (portal->nodes[1] == l)
  207.     {
  208.         *pp = portal->next[1];    
  209.         portal->nodes[1] = NULL;
  210.     }
  211. }
  212.  
  213. //============================================================================
  214.  
  215. void PrintPortal (portal_t *p)
  216. {
  217.     int            i;
  218.     winding_t    *w;
  219.     
  220.     w = p->winding;
  221.     for (i=0 ; i<w->numpoints ; i++)
  222.         printf ("(%5.0f,%5.0f,%5.0f)\n",w->p[i][0]
  223.         , w->p[i][1], w->p[i][2]);
  224. }
  225.  
  226. /*
  227. ================
  228. MakeHeadnodePortals
  229.  
  230. The created portals will face the global outside_node
  231. ================
  232. */
  233. #define    SIDESPACE    8
  234. void MakeHeadnodePortals (tree_t *tree)
  235. {
  236.     vec3_t        bounds[2];
  237.     int            i, j, n;
  238.     portal_t    *p, *portals[6];
  239.     plane_t        bplanes[6], *pl;
  240.     node_t *node;
  241.  
  242.     node = tree->headnode;
  243.  
  244. // pad with some space so there will never be null volume leafs
  245.     for (i=0 ; i<3 ; i++)
  246.     {
  247.         bounds[0][i] = tree->mins[i] - SIDESPACE;
  248.         bounds[1][i] = tree->maxs[i] + SIDESPACE;
  249.     }
  250.     
  251.     tree->outside_node.planenum = PLANENUM_LEAF;
  252.     tree->outside_node.brushlist = NULL;
  253.     tree->outside_node.portals = NULL;
  254.     tree->outside_node.contents = 0;
  255.  
  256.     for (i=0 ; i<3 ; i++)
  257.         for (j=0 ; j<2 ; j++)
  258.         {
  259.             n = j*3 + i;
  260.  
  261.             p = AllocPortal ();
  262.             portals[n] = p;
  263.             
  264.             pl = &bplanes[n];
  265.             memset (pl, 0, sizeof(*pl));
  266.             if (j)
  267.             {
  268.                 pl->normal[i] = -1;
  269.                 pl->dist = -bounds[j][i];
  270.             }
  271.             else
  272.             {
  273.                 pl->normal[i] = 1;
  274.                 pl->dist = bounds[j][i];
  275.             }
  276.             p->plane = *pl;
  277.             p->winding = BaseWindingForPlane (pl->normal, pl->dist);
  278.             AddPortalToNodes (p, node, &tree->outside_node);
  279.         }
  280.         
  281. // clip the basewindings by all the other planes
  282.     for (i=0 ; i<6 ; i++)
  283.     {
  284.         for (j=0 ; j<6 ; j++)
  285.         {
  286.             if (j == i)
  287.                 continue;
  288.             ChopWindingInPlace (&portals[i]->winding, bplanes[j].normal, bplanes[j].dist, ON_EPSILON);
  289.         }
  290.     }
  291. }
  292.  
  293. //===================================================
  294.  
  295.  
  296. /*
  297. ================
  298. BaseWindingForNode
  299. ================
  300. */
  301. #define    BASE_WINDING_EPSILON    0.001
  302. #define    SPLIT_WINDING_EPSILON    0.001
  303.  
  304. winding_t    *BaseWindingForNode (node_t *node)
  305. {
  306.     winding_t    *w;
  307.     node_t        *n;
  308.     plane_t        *plane;
  309.     vec3_t        normal;
  310.     vec_t        dist;
  311.  
  312.     w = BaseWindingForPlane (mapplanes[node->planenum].normal
  313.         , mapplanes[node->planenum].dist);
  314.  
  315.     // clip by all the parents
  316.     for (n=node->parent ; n && w ; )
  317.     {
  318.         plane = &mapplanes[n->planenum];
  319.  
  320.         if (n->children[0] == node)
  321.         {    // take front
  322.             ChopWindingInPlace (&w, plane->normal, plane->dist, BASE_WINDING_EPSILON);
  323.         }
  324.         else
  325.         {    // take back
  326.             VectorSubtract (vec3_origin, plane->normal, normal);
  327.             dist = -plane->dist;
  328.             ChopWindingInPlace (&w, normal, dist, BASE_WINDING_EPSILON);
  329.         }
  330.         node = n;
  331.         n = n->parent;
  332.     }
  333.  
  334.     return w;
  335. }
  336.  
  337. //============================================================
  338.  
  339. qboolean WindingIsTiny (winding_t *w);
  340.  
  341. /*
  342. ==================
  343. MakeNodePortal
  344.  
  345. create the new portal by taking the full plane winding for the cutting plane
  346. and clipping it by all of parents of this node
  347. ==================
  348. */
  349. void MakeNodePortal (node_t *node)
  350. {
  351.     portal_t    *new_portal, *p;
  352.     winding_t    *w;
  353.     vec3_t        normal;
  354.     float        dist;
  355.     int            side;
  356.  
  357.     w = BaseWindingForNode (node);
  358.  
  359.     // clip the portal by all the other portals in the node
  360.     for (p = node->portals ; p && w; p = p->next[side])    
  361.     {
  362.         if (p->nodes[0] == node)
  363.         {
  364.             side = 0;
  365.             VectorCopy (p->plane.normal, normal);
  366.             dist = p->plane.dist;
  367.         }
  368.         else if (p->nodes[1] == node)
  369.         {
  370.             side = 1;
  371.             VectorSubtract (vec3_origin, p->plane.normal, normal);
  372.             dist = -p->plane.dist;
  373.         }
  374.         else
  375.             Error ("CutNodePortals_r: mislinked portal");
  376.  
  377.         ChopWindingInPlace (&w, normal, dist, 0.1);
  378.     }
  379.  
  380.     if (!w)
  381.     {
  382.         return;
  383.     }
  384.  
  385.     if (WindingIsTiny (w))
  386.     {
  387.         c_tinyportals++;
  388.         FreeWinding (w);
  389.         return;
  390.     }
  391.  
  392.  
  393.     new_portal = AllocPortal ();
  394.     new_portal->plane = mapplanes[node->planenum];
  395.     new_portal->onnode = node;
  396.     new_portal->winding = w;    
  397.     AddPortalToNodes (new_portal, node->children[0], node->children[1]);
  398. }
  399.  
  400.  
  401. /*
  402. ==============
  403. SplitNodePortals
  404.  
  405. Move or split the portals that bound node so that the node's
  406. children have portals instead of node.
  407. ==============
  408. */
  409. void SplitNodePortals (node_t *node)
  410. {
  411.     portal_t    *p, *next_portal, *new_portal;
  412.     node_t        *f, *b, *other_node;
  413.     int            side;
  414.     plane_t        *plane;
  415.     winding_t    *frontwinding, *backwinding;
  416.  
  417.     plane = &mapplanes[node->planenum];
  418.     f = node->children[0];
  419.     b = node->children[1];
  420.  
  421.     for (p = node->portals ; p ; p = next_portal)    
  422.     {
  423.         if (p->nodes[0] == node)
  424.             side = 0;
  425.         else if (p->nodes[1] == node)
  426.             side = 1;
  427.         else
  428.             Error ("CutNodePortals_r: mislinked portal");
  429.         next_portal = p->next[side];
  430.  
  431.         other_node = p->nodes[!side];
  432.         RemovePortalFromNode (p, p->nodes[0]);
  433.         RemovePortalFromNode (p, p->nodes[1]);
  434.  
  435. //
  436. // cut the portal into two portals, one on each side of the cut plane
  437. //
  438.         ClipWindingEpsilon (p->winding, plane->normal, plane->dist,
  439.             SPLIT_WINDING_EPSILON, &frontwinding, &backwinding);
  440.  
  441.         if (frontwinding && WindingIsTiny(frontwinding))
  442.         {
  443.             FreeWinding (frontwinding);
  444.             frontwinding = NULL;
  445.             c_tinyportals++;
  446.         }
  447.  
  448.         if (backwinding && WindingIsTiny(backwinding))
  449.         {
  450.             FreeWinding (backwinding);
  451.             backwinding = NULL;
  452.             c_tinyportals++;
  453.         }
  454.  
  455.         if (!frontwinding && !backwinding)
  456.         {    // tiny windings on both sides
  457.             continue;
  458.         }
  459.  
  460.         if (!frontwinding)
  461.         {
  462.             FreeWinding (backwinding);
  463.             if (side == 0)
  464.                 AddPortalToNodes (p, b, other_node);
  465.             else
  466.                 AddPortalToNodes (p, other_node, b);
  467.             continue;
  468.         }
  469.         if (!backwinding)
  470.         {
  471.             FreeWinding (frontwinding);
  472.             if (side == 0)
  473.                 AddPortalToNodes (p, f, other_node);
  474.             else
  475.                 AddPortalToNodes (p, other_node, f);
  476.             continue;
  477.         }
  478.         
  479.     // the winding is split
  480.         new_portal = AllocPortal ();
  481.         *new_portal = *p;
  482.         new_portal->winding = backwinding;
  483.         FreeWinding (p->winding);
  484.         p->winding = frontwinding;
  485.  
  486.         if (side == 0)
  487.         {
  488.             AddPortalToNodes (p, f, other_node);
  489.             AddPortalToNodes (new_portal, b, other_node);
  490.         }
  491.         else
  492.         {
  493.             AddPortalToNodes (p, other_node, f);
  494.             AddPortalToNodes (new_portal, other_node, b);
  495.         }
  496.     }
  497.  
  498.     node->portals = NULL;
  499. }
  500.  
  501.  
  502. /*
  503. ================
  504. CalcNodeBounds
  505. ================
  506. */
  507. void CalcNodeBounds (node_t *node)
  508. {
  509.     portal_t    *p;
  510.     int            s;
  511.     int            i;
  512.  
  513.     // calc mins/maxs for both leafs and nodes
  514.     ClearBounds (node->mins, node->maxs);
  515.     for (p = node->portals ; p ; p = p->next[s])    
  516.     {
  517.         s = (p->nodes[1] == node);
  518.         for (i=0 ; i<p->winding->numpoints ; i++)
  519.             AddPointToBounds (p->winding->p[i], node->mins, node->maxs);
  520.     }
  521. }
  522.  
  523.  
  524. /*
  525. ==================
  526. MakeTreePortals_r
  527. ==================
  528. */
  529. void MakeTreePortals_r (node_t *node)
  530. {
  531.     int        i;
  532.  
  533.     CalcNodeBounds (node);
  534.     if (node->mins[0] >= node->maxs[0])
  535.     {
  536.         printf ("WARNING: node without a volume\n");
  537.     }
  538.  
  539.     for (i=0 ; i<3 ; i++)
  540.     {
  541.         if (node->mins[i] < -8000 || node->maxs[i] > 8000)
  542.         {
  543.             printf ("WARNING: node with unbounded volume\n");
  544.             break;
  545.         }
  546.     }
  547.     if (node->planenum == PLANENUM_LEAF)
  548.         return;
  549.  
  550.     MakeNodePortal (node);
  551.     SplitNodePortals (node);
  552.  
  553.     MakeTreePortals_r (node->children[0]);
  554.     MakeTreePortals_r (node->children[1]);
  555. }
  556.  
  557. /*
  558. ==================
  559. MakeTreePortals
  560. ==================
  561. */
  562. void MakeTreePortals (tree_t *tree)
  563. {
  564.     MakeHeadnodePortals (tree);
  565.     MakeTreePortals_r (tree->headnode);
  566. }
  567.  
  568. /*
  569. =========================================================
  570.  
  571. FLOOD ENTITIES
  572.  
  573. =========================================================
  574. */
  575.  
  576. /*
  577. =============
  578. FloodPortals_r
  579. =============
  580. */
  581. void FloodPortals_r (node_t *node, int dist)
  582. {
  583.     portal_t    *p;
  584.     int            s;
  585.  
  586.     node->occupied = dist;
  587.  
  588.     for (p=node->portals ; p ; p = p->next[s])
  589.     {
  590.         s = (p->nodes[1] == node);
  591.  
  592.         if (p->nodes[!s]->occupied)
  593.             continue;
  594.  
  595.         if (!Portal_EntityFlood (p, s))
  596.             continue;
  597.  
  598.         FloodPortals_r (p->nodes[!s], dist+1);
  599.     }
  600. }
  601.  
  602. /*
  603. =============
  604. PlaceOccupant
  605. =============
  606. */
  607. qboolean PlaceOccupant (node_t *headnode, vec3_t origin, entity_t *occupant)
  608. {
  609.     node_t    *node;
  610.     vec_t    d;
  611.     plane_t    *plane;
  612.  
  613.     // find the leaf to start in
  614.     node = headnode;
  615.     while (node->planenum != PLANENUM_LEAF)
  616.     {
  617.         plane = &mapplanes[node->planenum];
  618.         d = DotProduct (origin, plane->normal) - plane->dist;
  619.         if (d >= 0)
  620.             node = node->children[0];
  621.         else
  622.             node = node->children[1];
  623.     }
  624.  
  625.     if (node->contents == CONTENTS_SOLID)
  626.         return false;
  627.     node->occupant = occupant;
  628.  
  629.     FloodPortals_r (node, 1);
  630.  
  631.     return true;
  632. }
  633.  
  634. /*
  635. =============
  636. FloodEntities
  637.  
  638. Marks all nodes that can be reached by entites
  639. =============
  640. */
  641. qboolean FloodEntities (tree_t *tree)
  642. {
  643.     int        i;
  644.     vec3_t    origin;
  645.     char    *cl;
  646.     qboolean    inside;
  647.     node_t *headnode;
  648.  
  649.     headnode = tree->headnode;
  650.     qprintf ("--- FloodEntities ---\n");
  651.     inside = false;
  652.     tree->outside_node.occupied = 0;
  653.  
  654.     for (i=1 ; i<num_entities ; i++)
  655.     {
  656.         GetVectorForKey (&entities[i], "origin", origin);
  657.         if (VectorCompare(origin, vec3_origin))
  658.             continue;
  659.  
  660.         cl = ValueForKey (&entities[i], "classname");
  661.         origin[2] += 1;    // so objects on floor are ok
  662.  
  663.         // nudge playerstart around if needed so clipping hulls allways
  664.         // have a vlaid point
  665.         if (!strcmp (cl, "info_player_start"))
  666.         {
  667.             int    x, y;
  668.  
  669.             for (x=-16 ; x<=16 ; x += 16)
  670.             {
  671.                 for (y=-16 ; y<=16 ; y += 16)
  672.                 {
  673.                     origin[0] += x;
  674.                     origin[1] += y;
  675.                     if (PlaceOccupant (headnode, origin, &entities[i]))
  676.                     {
  677.                         inside = true;
  678.                         goto gotit;
  679.                     }
  680.                     origin[0] -= x;
  681.                     origin[1] -= y;
  682.                 }
  683.             }
  684. gotit: ;
  685.         }
  686.         else
  687.         {
  688.             if (PlaceOccupant (headnode, origin, &entities[i]))
  689.                 inside = true;
  690.         }
  691.     }
  692.  
  693.     if (!inside)
  694.     {
  695.         qprintf ("no entities in open -- no filling\n");
  696.     }
  697.     else if (tree->outside_node.occupied)
  698.     {
  699.         qprintf ("entity reached from outside -- no filling\n");
  700.     }
  701.  
  702.     return (qboolean)(inside && !tree->outside_node.occupied);
  703. }
  704.  
  705. /*
  706. =========================================================
  707.  
  708. FLOOD AREAS
  709.  
  710. =========================================================
  711. */
  712.  
  713. int        c_areas;
  714.  
  715. /*
  716. =============
  717. FloodAreas_r
  718. =============
  719. */
  720. void FloodAreas_r (node_t *node)
  721. {
  722.     portal_t    *p;
  723.     int            s;
  724.     bspbrush_t    *b;
  725.     entity_t    *e;
  726.  
  727.     if (node->contents == CONTENTS_AREAPORTAL)
  728.     {
  729.         // this node is part of an area portal
  730.         b = node->brushlist;
  731.         e = &entities[b->original->entitynum];
  732.  
  733.         // if the current area has allready touched this
  734.         // portal, we are done
  735.         if (e->portalareas[0] == c_areas || e->portalareas[1] == c_areas)
  736.             return;
  737.  
  738.         // note the current area as bounding the portal
  739.         if (e->portalareas[1])
  740.         {
  741.             printf ("WARNING: areaportal entity %i touches > 2 areas\n", b->original->entitynum);
  742.             return;
  743.         }
  744.         if (e->portalareas[0])
  745.             e->portalareas[1] = c_areas;
  746.         else
  747.             e->portalareas[0] = c_areas;
  748.  
  749.         return;
  750.     }
  751.  
  752.     if (node->area)
  753.         return;        // allready got it
  754.     node->area = c_areas;
  755.  
  756.     for (p=node->portals ; p ; p = p->next[s])
  757.     {
  758.         s = (p->nodes[1] == node);
  759. #if 0
  760.         if (p->nodes[!s]->occupied)
  761.             continue;
  762. #endif
  763.         if (!Portal_EntityFlood (p, s))
  764.             continue;
  765.  
  766.         FloodAreas_r (p->nodes[!s]);
  767.     }
  768. }
  769.  
  770. /*
  771. =============
  772. FindAreas_r
  773.  
  774. Just decend the tree, and for each node that hasn't had an
  775. area set, flood fill out from there
  776. =============
  777. */
  778. void FindAreas_r (node_t *node)
  779. {
  780.     if (node->planenum != PLANENUM_LEAF)
  781.     {
  782.         FindAreas_r (node->children[0]);
  783.         FindAreas_r (node->children[1]);
  784.         return;
  785.     }
  786.  
  787.     if (node->area)
  788.         return;        // allready got it
  789.  
  790.     if (node->contents & CONTENTS_SOLID)
  791.         return;
  792.  
  793.     if (!node->occupied)
  794.         return;            // not reachable by entities
  795.  
  796.     // area portals are allways only flooded into, never
  797.     // out of
  798.     if (node->contents == CONTENTS_AREAPORTAL)
  799.         return;
  800.  
  801.     c_areas++;
  802.     FloodAreas_r (node);
  803. }
  804.  
  805. /*
  806. =============
  807. SetAreaPortalAreas_r
  808.  
  809. Just decend the tree, and for each node that hasn't had an
  810. area set, flood fill out from there
  811. =============
  812. */
  813. void SetAreaPortalAreas_r (node_t *node)
  814. {
  815.     bspbrush_t    *b;
  816.     entity_t    *e;
  817.  
  818.     if (node->planenum != PLANENUM_LEAF)
  819.     {
  820.         SetAreaPortalAreas_r (node->children[0]);
  821.         SetAreaPortalAreas_r (node->children[1]);
  822.         return;
  823.     }
  824.  
  825.     if (node->contents == CONTENTS_AREAPORTAL)
  826.     {
  827.         if (node->area)
  828.             return;        // allready set
  829.  
  830.         b = node->brushlist;
  831.         e = &entities[b->original->entitynum];
  832.         node->area = e->portalareas[0];
  833.         if (!e->portalareas[1])
  834.         {
  835.             printf ("WARNING: areaportal entity %i doesn't touch two areas\n", b->original->entitynum);
  836.             return;
  837.         }
  838.     }
  839. }
  840.  
  841. /*
  842. =============
  843. EmitAreaPortals
  844.  
  845. =============
  846. */
  847. void EmitAreaPortals (node_t *headnode)
  848. {
  849.     int                i, j;
  850.     entity_t        *e;
  851.     dareaportal_t    *dp;
  852.  
  853.     if (c_areas > MAX_MAP_AREAS)
  854.         Error ("MAX_MAP_AREAS");
  855.     numareas = c_areas+1;
  856.     numareaportals = 1;        // leave 0 as an error
  857.  
  858.     for (i=1 ; i<=c_areas ; i++)
  859.     {
  860.         dareas[i].firstareaportal = numareaportals;
  861.         for (j=0 ; j<num_entities ; j++)
  862.         {
  863.             e = &entities[j];
  864.             if (!e->areaportalnum)
  865.                 continue;
  866.             dp = &dareaportals[numareaportals];
  867.             if (e->portalareas[0] == i)
  868.             {
  869.                 dp->portalnum = e->areaportalnum;
  870.                 dp->otherarea = e->portalareas[1];
  871.                 numareaportals++;
  872.             }
  873.             else if (e->portalareas[1] == i)
  874.             {
  875.                 dp->portalnum = e->areaportalnum;
  876.                 dp->otherarea = e->portalareas[0];
  877.                 numareaportals++;
  878.             }
  879.         }
  880.         dareas[i].numareaportals = numareaportals - dareas[i].firstareaportal;
  881.     }
  882.  
  883.     qprintf ("%5i numareas\n", numareas);
  884.     qprintf ("%5i numareaportals\n", numareaportals);
  885. }
  886.  
  887. /*
  888. =============
  889. FloodAreas
  890.  
  891. Mark each leaf with an area, bounded by CONTENTS_AREAPORTAL
  892. =============
  893. */
  894. void FloodAreas (tree_t *tree)
  895. {
  896.     qprintf ("--- FloodAreas ---\n");
  897.     FindAreas_r (tree->headnode);
  898.     SetAreaPortalAreas_r (tree->headnode);
  899.     qprintf ("%5i areas\n", c_areas);
  900. }
  901.  
  902. //======================================================
  903.  
  904. int        c_outside;
  905. int        c_inside;
  906. int        c_solid;
  907.  
  908. void FillOutside_r (node_t *node)
  909. {
  910.     if (node->planenum != PLANENUM_LEAF)
  911.     {
  912.         FillOutside_r (node->children[0]);
  913.         FillOutside_r (node->children[1]);
  914.         return;
  915.     }
  916.  
  917.     // anything not reachable by an entity
  918.     // can be filled away
  919.     if (!node->occupied)
  920.     {
  921.         if (node->contents != CONTENTS_SOLID)
  922.         {
  923.             c_outside++;
  924.             node->contents = CONTENTS_SOLID;
  925.         }
  926.         else
  927.             c_solid++;
  928.     }
  929.     else
  930.         c_inside++;
  931.  
  932. }
  933.  
  934. /*
  935. =============
  936. FillOutside
  937.  
  938. Fill all nodes that can't be reached by entities
  939. =============
  940. */
  941. void FillOutside (node_t *headnode)
  942. {
  943.     c_outside = 0;
  944.     c_inside = 0;
  945.     c_solid = 0;
  946.     qprintf ("--- FillOutside ---\n");
  947.     FillOutside_r (headnode);
  948.     qprintf ("%5i solid leafs\n", c_solid);
  949.     qprintf ("%5i leafs filled\n", c_outside);
  950.     qprintf ("%5i inside leafs\n", c_inside);
  951. }
  952.  
  953.  
  954. //==============================================================
  955.  
  956. /*
  957. ============
  958. FindPortalSide
  959.  
  960. Finds a brush side to use for texturing the given portal
  961. ============
  962. */
  963. void FindPortalSide (portal_t *p)
  964. {
  965.     int            viscontents;
  966.     bspbrush_t    *bb;
  967.     mapbrush_t    *brush;
  968.     node_t        *n;
  969.     int            i,j;
  970.     int            planenum;
  971.     side_t        *side, *bestside;
  972.     float        dot, bestdot;
  973.     plane_t        *p1, *p2;
  974.  
  975.     // decide which content change is strongest
  976.     // solid > lava > water, etc
  977.     viscontents = VisibleContents (p->nodes[0]->contents ^ p->nodes[1]->contents);
  978.     if (!viscontents)
  979.         return;
  980.  
  981.     planenum = p->onnode->planenum;
  982.     bestside = NULL;
  983.     bestdot = 0;
  984.  
  985.     for (j=0 ; j<2 ; j++)
  986.     {
  987.         n = p->nodes[j];
  988.         p1 = &mapplanes[p->onnode->planenum];
  989.         for (bb=n->brushlist ; bb ; bb=bb->next)
  990.         {
  991.             brush = bb->original;
  992.             if ( !(brush->contents & viscontents) )
  993.                 continue;
  994.             for (i=0 ; i<brush->numsides ; i++)
  995.             {
  996.                 side = &brush->original_sides[i];
  997.                 if (side->bevel)
  998.                     continue;
  999.                 if (side->texinfo == TEXINFO_NODE)
  1000.                     continue;        // non-visible
  1001.                 if ((side->planenum&~1) == planenum)
  1002.                 {    // exact match
  1003.                     bestside = &brush->original_sides[i];
  1004.                     goto gotit;
  1005.                 }
  1006.                 // see how close the match is
  1007.                 p2 = &mapplanes[side->planenum&~1];
  1008.                 dot = DotProduct (p1->normal, p2->normal);
  1009.                 if (dot > bestdot)
  1010.                 {
  1011.                     bestdot = dot;
  1012.                     bestside = side;
  1013.                 }
  1014.             }
  1015.         }
  1016.     }
  1017.  
  1018. gotit:
  1019.     if (!bestside)
  1020.         qprintf ("WARNING: side not found for portal\n");
  1021.  
  1022.     p->sidefound = true;
  1023.     p->side = bestside;
  1024. }
  1025.  
  1026.  
  1027. /*
  1028. ===============
  1029. MarkVisibleSides_r
  1030.  
  1031. ===============
  1032. */
  1033. void MarkVisibleSides_r (node_t *node)
  1034. {
  1035.     portal_t    *p;
  1036.     int            s;
  1037.  
  1038.     if (node->planenum != PLANENUM_LEAF)
  1039.     {
  1040.         MarkVisibleSides_r (node->children[0]);
  1041.         MarkVisibleSides_r (node->children[1]);
  1042.         return;
  1043.     }
  1044.  
  1045.     // empty leafs are never boundary leafs
  1046.     if (!node->contents)
  1047.         return;
  1048.  
  1049.     // see if there is a visible face
  1050.     for (p=node->portals ; p ; p = p->next[!s])
  1051.     {
  1052.         s = (p->nodes[0] == node);
  1053.         if (!p->onnode)
  1054.             continue;        // edge of world
  1055.         if (!p->sidefound)
  1056.             FindPortalSide (p);
  1057.         if (p->side)
  1058.             p->side->visible = true;
  1059.     }
  1060.  
  1061. }
  1062.  
  1063. /*
  1064. =============
  1065. MarkVisibleSides
  1066.  
  1067. =============
  1068. */
  1069. void MarkVisibleSides (tree_t *tree, int startbrush, int endbrush)
  1070. {
  1071.     int        i, j;
  1072.     mapbrush_t    *mb;
  1073.     int        numsides;
  1074.  
  1075.     qprintf ("--- MarkVisibleSides ---\n");
  1076.  
  1077.     // clear all the visible flags
  1078.     for (i=startbrush ; i<endbrush ; i++)
  1079.     {
  1080.         mb = &mapbrushes[i];
  1081.  
  1082.         numsides = mb->numsides;
  1083.         for (j=0 ; j<numsides ; j++)
  1084.             mb->original_sides[j].visible = false;
  1085.     }
  1086.  
  1087.     // set visible flags on the sides that are used by portals
  1088.     MarkVisibleSides_r (tree->headnode);
  1089. }
  1090.  
  1091.